//给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
//
//
//
// 示例 1:
//
//
//输入: nums = [0,1]
//输出: 2
//说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
//
// 示例 2:
//
//
//输入: nums = [0,1,0]
//输出: 2
//说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁵
// nums[i] 不是 0 就是 1
//
//
//
//
// 注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/
// Related Topics 数组 哈希表 前缀和 👍 41 👎 0

package leetcode.editor.cn;

import java.util.HashMap;

@SuppressWarnings("all")
//Java：0 和 1 个数相同的子数组
class 零和一个数相同的子数组 {
    public static void main(String[] args) {
        Solution solution = new 零和一个数相同的子数组().new Solution();
        // TO TEST
        int[] nums ={0,1,1,1,1,0,0,0};
        System.out.println(solution.findMaxLength(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findMaxLength(int[] nums) {

            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);
            int pre_sum = 0;
            int ret = 0;
            for (int i = 0; i < nums.length; i++) {
                pre_sum += nums[i] == 0 ? -1 : 1;
                if (map.containsKey(pre_sum)) {
                    ret = Math.max(ret, i - map.get(pre_sum));
                } else {
                    map.put(pre_sum, i);
                }
            }
            return ret;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
